/**
 * 链表节点定义
 */
class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}

/**
 * 排序链表（归并排序）
 * 给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。
 * 
 * 算法思路：
 * 使用归并排序的思想：
 * 1. 找到链表的中点，将链表分成两部分
 * 2. 递归地对两部分进行排序
 * 3. 合并两个已排序的链表
 * 
 * 时间复杂度：O(n log n)，其中 n 是链表的长度
 * 空间复杂度：O(log n)，递归调用栈的深度为 log n
 */
function sortList(head: ListNode | null): ListNode | null {
    // 递归终止条件：链表为空或只有一个节点
    if (!head || !head.next) return head;
    
    // 使用快慢指针找到链表中点
    // slow 最终指向中点（或中点前一个节点），fast 指向末尾
    let pre: ListNode | null = null;  // 中点前一个节点，用于分割链表
    let slow: ListNode | null = head;
    let fast: ListNode | null = head;
    
    while (fast && fast.next) {
        pre = slow;
        slow = slow!.next;
        fast = fast.next.next;
    }
    
    // 将链表从中间断开，分成两部分
    // pre 此时指向中点前一个节点，slow 指向中点
    if (pre) {
        pre.next = null;
    }
    
    // 递归排序两部分
    let head1 = sortList(head);      // 排序前半部分
    let head2 = sortList(slow);      // 排序后半部分
    
    // 合并两个已排序的链表
    return merge(head1, head2);
}

/**
 * 合并两个有序链表（辅助函数）
 * 使用双指针方法合并两个已排序的链表
 * 
 * @param list1 第一个有序链表的头节点
 * @param list2 第二个有序链表的头节点
 * @returns 合并后的有序链表的头节点
 */
function merge(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    // 创建虚拟头节点（哨兵节点），简化代码逻辑
    const dummy = new ListNode();
    // cur 指向新链表的末尾
    let cur: ListNode | null = dummy;
    
    // 当两个链表都不为空时，比较节点值，将较小的节点加入新链表
    while (list1 && list2) {
        if (list1.val < list2.val) {
            // 把 list1 的当前节点加到新链表中
            cur.next = list1;
            list1 = list1.next;
        } else {
            // 把 list2 的当前节点加到新链表中
            // 注：相等的情况加哪个节点都是可以的
            cur.next = list2;
            list2 = list2.next;
        }
        cur = cur.next;
    }
    
    // 拼接剩余链表（其中一个链表已经遍历完，另一个链表还有剩余节点）
    cur.next = list1 ?? list2;
    
    return dummy.next;
}